package cn.com.leetcode.dp;

public class Demo392_after {
    public static void main(String[] args) {
        String s = "adya";
        String t = "ahbgdc";
        Demo392_after demo392_after = new Demo392_after();
        boolean flag = demo392_after.isSubsequence(s, t);
        System.out.println(flag);
    }

    /**
     * after
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        t = " " + t;
        int length = t.length();
        int[][] dp = new int[26][length];   /*
                                             dp[i][j] 表示 在第 t 串 j 位置之后是否有匹配字符 'a' + i 的字符,若有，
                                             则返回 t 串 j 位置之后，字符 'a' + i 的位置，若没有，返回 -1
                                            */
        for (int i = 0; i < 26; i++) {
            int p = -1;
            for (int j = length - 1; j >= 0; j--) { // 从后往前记录dp
                dp[i][j] = p;
                if (t.charAt(j) - 'a' == i) {
                    p = j;
                }
            }
        }
        for (int i = 0; i < 26; i++) {

        }
        int sIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            sIndex = dp[s.charAt(i) - 'a'][sIndex];
            if (sIndex == -1) {
                return false;
            }

        }
        return true;
    }

    public boolean isSubsequence1(String s, String t) {

        // 预处理
        t = " " + t; // 开头加一个空字符作为匹配入口
        int n = t.length();
        int[][] dp = new int[n][26]; // 记录每个位置的下一个ch的位置
        for (char ch = 0; ch < 26; ch++) {
            int p = -1;
            for (int i = n - 1; i >= 0; i--) { // 从后往前记录dp
                dp[i][ch] = p;
                if (t.charAt(i) == ch + 'a') p = i;
            }
        }

        // 匹配
        int i = 0;
        for (char ch : s.toCharArray()) { // 跳跃遍历
            i = dp[i][ch - 'a'];
            if (i == -1) return false;
        }
        return true;
    }

}
